class Solution 
{
public:
    bool isUnique(string ast)
    {
        //利用鸽巢原理优化时间复杂度
        if(ast.size() > 26)
            return false;
        //利用位图来做查重()
        int bitmap = 0;
        
        for(auto ch : ast)
        {
            int i = ch - 'a';
            
            if(((bitmap>>i) & 1) == 1)
                return false;
            else
                bitmap |= (1 << i);
        }
        return true;

    }
};

class Solution {
public:
    int missingNumber(vector<int>& nums) 
    {
        //高斯求和
        int sum = 0;
        for(auto x : nums)
            sum += x;
        
        int n = nums.size();
        int total = n * (n+1) / 2;

        return total - sum;<Paste>
//        int ret = 0;
//        for(int i = 0; i < nums.size(); i++)
//        {
//            ret ^= nums[i];
//        }
//
//        for(int i = 0; i <= nums.size(); i++)
//        {
//            ret ^= i;
//        }
//        return ret;
    }
};

class Solution {
public:
    int getSum(int a, int b) 
    {
        if(b == 0)
            return a;

        int i = a, j = b;
        while(true)
        {
            int x = i ^ j;
            int y = (i&j) << 1;
            i = x;
            j = y;
            if(y == 0)
                return x;
        }
    }
};

class Solution {
public:
    int singleNumber(vector<int>& nums) 
    {
        int ret = 0;
        for(int i = 0; i < 32; i++)
        {
            int sum = 0;
            for(auto x : nums)
            {
                if(((x>>i)&1) == 1)
                    sum++;
                sum %= 3;
            }
            if(sum == 1)
                ret |= (sum << i);
        }
        return ret;
    }
};

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) 
    {
        //1.将所有的数异或在一起
        int tmp = 0;
        for(auto e : nums)
            tmp ^= e;
        for(int i = 1; i <= nums.size()+2; i++)
            tmp ^= i;
        
        //2.找出a、b中比特位不同的那一位
        int diff = 0;
        for(;;)
        {
            if(((tmp >> diff)&1) == 1)
                break;
            diff++;
        }

        //根据diff位的不同，划分两个类异或
        int a = 0, b = 0;
        for(auto e: nums)
        {
            if(((e >> diff) & 1) == 1)
                a ^= e;
            else
                b ^= e;
        }

        for(int i = 1; i <= nums.size() + 2; i++)
        {
            if(((i >> diff) & 1) == 1)
                a ^= i;
            else
                b ^= i;
        }

        return {a,b};
    }
};

class Solution {
public:
//    string modifyString(string s) 
//    {
//        int hash[26] = {0};
//        //统计一下出现的字符
//        for(int i = 0;i < s.size();i++)
//        {
//            if(s[i] != '?')
//                hash[s[i] - 'a']++;
//        }
//        
//        for(int i = 0; i < s.size();i++)
//        {
//            if(s[i] == '?')
//            {
//                if(i == 0)
//                {
//                    for(int j = 0;j < 26; j++)
//                    {
//                        if(('a' + j) != s[i+1])
//                        {
//                            s[i] = 'a'+ j;
//                            break;
//                        }
//                    }
//                }
//                else if(i == s.size() - 1)
//                {
//                    for(int j = 0;j < 26; j++)
//                    {
//                        if(('a' + j) != s[i - 1])
//                        {
//                            s[i] = 'a'+ j;
//                            break;
//                        }
//                    }
//                }
//                else
//                {
//                    for(int j = 0;j < 26; j++)
//                    {
//                        if(('a' + j) != s[i-1] && ('a' + j) != s[i+1])
//                        {
//                            s[i] = 'a'+ j;
//                            break;
//                        }
//                    }
//                }
//            }
//        }
//
//        return s;
//        
//    }
 string modifyString(string s) 
    {
        int n = s.size();
        for(int i = 0; i < n; ++i)
        {
            if(s[i] == '?')
            {
                for(char ch = 'a'; ch <= 'c'; ch++)
                {
                    if(i == 0)
                    {
                        if(s[i+1] == ch)
                            continue;
                        s[i] = ch;
                    }   
                    else if(i == n - 1) 
                    {
                        if(s[i - 1] == ch)
                            continue;
                        s[i] = ch;
                    }   
                    else
                    {
                        if(s[i + 1] == ch || s[i - 1] == ch)
                            continue;
                        s[i] = ch;
                    }             
                }
            }
        }
        return s;
        
    }
};

//提莫攻击
class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) 
    {
        int sum = 0;
        for(int i = 0; i < timeSeries.size(); ++i)
        {
            if(i != timeSeries.size() - 1)
            {
                if(timeSeries[i+1] - timeSeries[i] >= duration)
                    sum += duration;
                else
                    sum += (timeSeries[i+1] - timeSeries[i]);
            }
        }

        //需要再统计一个duration，因为最后一个中毒时间在循环里没加。
        return sum += duration;

    }
};

class Solution {
public:
    // string convert(string s, int numRows) 
    // {
    //     if(numRows == 1)
    //         return s;
            
    //     int n = s.size();
    //     int d = 2 * numRows - 2;//通过画图找规律可以得到公差

    //     string ret;
        
    //     //处理第一行
    //     for(int i = 0; i < n;i += d)
    //     {
    //         ret += s[i];
    //     }

    //     //处理 1 到 numRows-2 行
    //     for(int i = 1; i < numRows - 1; i++)
    //     {
    //         for(int j = i, k = d - j; j < n || k < n; j += d, k += d)
    //         {
    //             //需要注意越界情况
    //             if(j < n)
    //                 ret += s[j];
    //             if(k < n)
    //                 ret += s[k];
    //         }
    //     }

    //     //处理最后一行
    //     for(int i = numRows - 1; i < n; i += d)
    //     {
    //         ret += s[i];
    //     }
    //     return ret;
    // }
        string convert(string s, int numRows) 
    {
        //边界情况
        if(numRows == 1)
            return s;
        
        vector<string> rows(numRows);//用于保存模拟N形后的子串
        int flag = -1, i = 0;;
        for(char ch : s)
        {
            
            rows[i].push_back(ch);

            if(i == 0 || i == numRows - 1)
                flag = -flag;
            
            i += flag;
        }

        string ret;
        for(const string &row : rows)
        {
            ret += row; 
        }

        return ret;
    }
};